/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */

var copyRandomList = function (head) {
    if (!head) {
        return
    }
    // 创建cur 复制head
    let cur = head
    let dummy = new Node()
    let newNode = new Node()
    dummy.next = newNode
    // 用来储存已经遍历过的结点
    let map = new Map()
    // 先循环遍历将next的全部copy下来
    while (cur) {
        newNode.val = cur.val
        newNode.next = cur.next ? new Node() : null
        map.set(cur, newNode)
        cur = cur.next
        newNode = newNode.next
    }
    // 将两个结点定位到两个链表的头节点
    cur = head
    newNode = dummy.next
    // 循环遍历将random全部copy下来
    while (cur) {
        newNode.random = map.has(cur) ? map.get(cur.random) : null
        cur = cur.next
        newNode = newNode.next
    }
    return dummy.next
};